package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

var sum int
var m map[*TreeNode]int // 子树和

func findTilt(root *TreeNode) int {
	sum = 0
	m = make(map[*TreeNode]int)
	getSum(root)
	dfs(root)
	return sum
}

func getSum(root *TreeNode) int {
	if root == nil {
		return 0
	}
	left := getSum(root.Left)
	right := getSum(root.Right)
	val := left + right + root.Val
	m[root] = val
	return val
}

func dfs(root *TreeNode) {
	if root == nil {
		return
	}
	left := m[root.Left]
	right := m[root.Right]
	var tilt int
	if left < right {
		tilt = right - left
	} else {
		tilt = left - right
	}
	sum += tilt
	dfs(root.Left)
	dfs(root.Right)
}

func main() {
	root := &TreeNode{
		Val: 4,
		Left: &TreeNode{
			Val: 2,
			Left: &TreeNode{
				Val: 3,
			},
			Right: &TreeNode{
				Val: 5,
			},
		},
		Right: &TreeNode{
			Val: 9,
			Right: &TreeNode{
				Val: 7,
			},
		},
	}
	println(findTilt(root))
}
